package org.example.myleet.p870;

import java.util.*;

public class Solution {
    public int[] advantageCount(int[] nums1, int[] nums2) {
        //贪心：田忌赛马，对nums2中的数字，在nums1中挑出刚刚好大于它的数字
        //保留nums2的顺序用于最后组织答案
        int[] copyNum2 = new int[nums2.length];
        System.arraycopy(nums2, 0, copyNum2, 0, nums2.length);
        //nums1和nums2都进行升序排序，然后通过田忌赛马的方式找到产生优势的匹配值
        Arrays.sort(nums2);
        Arrays.sort(nums1);
        //nums1中可能有些不能产生优势的情况，这些就记录起来，最后凑数
        Queue<Integer> nums1Unmatched = new LinkedList<>();
        //记录nums2中对应的仅仅可以产生优势的nums1，由于nums2的数字可能存在重复，因此使用队列记录相同情况下nums1中有哪些可用数字
        Map<Integer, Queue<Integer>> nums2MapNums1 = new HashMap<>();
        int i = 0, j = 0;
        while (i < nums1.length) {
            if (nums1[i] <= nums2[j]) {
                //不能产生优势，保留
                nums1Unmatched.add(nums1[i]);
                ++i;
                continue;
            }
            //产生优势，记录优势
            Queue<Integer> nums1Queue = nums2MapNums1.getOrDefault(nums2[j], new LinkedList<>());
            nums1Queue.offer(nums1[i]);
            nums2MapNums1.put(nums2[j], nums1Queue);
            ++i;
            ++j;
        }
        int[] res = new int[nums1.length];
        for (j = 0; j < copyNum2.length; ++j) {
            Queue<Integer> nums1Queue = nums2MapNums1.getOrDefault(copyNum2[j], new LinkedList<>());
            if (nums1Queue.size() < 1) {
                //nums2中的数字太强，找不到可以产生优势的nums1的数字，用凑数的顶上
                res[j] = nums1Unmatched.poll();
            } else {
                //产生优势，使用优势数字
                res[j] = nums1Queue.poll();
            }
        }
        return res;
    }
}
